\documentclass[a4paper]{article}
\usepackage[affil-it]{authblk}
\usepackage[backend=bibtex,style=numeric]{biblatex}
\usepackage{geometry}
\geometry{margin=1.5cm}
\usepackage{amsmath}
\usepackage{graphicx}

\title{Numerical Analysis Theoretical Assignment Report}
\author{Liang Yue \quad Student ID: 3220100159}
\affil{Email: 3220100159@zju.edu.cn \\ Major and Class: Information and Computational Science 2201, Zhejiang University}
\date{Due Date: \today}

\begin{document}
	
\maketitle
	
\section*{I.}
	Assume $p(x)=ax^3+bx^2+cx+d$;\\
	The derivative of p(x):$p'(x)=3ax^2+2bx+c$;\\
	The 2th derivative of p(x):$p''(x)=6ax+2b$;\\
	A natural cubic spline satisfies $s''(f;a)=0$,$s''(f;b)=0$;\\
	Because s(x) is twice continuous and twice differentiable, we have to ensure that p(x) and $(2-x)^3$ match at x=1 along with their first and second derivatives.\\
	\[p(0)=d=0,p(1)=a+b+c+d=1,p'(1)=3a+2b+c=-3,p''(1)=6a+2b=6\]
	\[a=7,b=-18,c=12,d=0\]
	Therefore $p(x)=7x^3-18x^2+12x$.\\
	$p''(0)=-36=s''(0)\ne 0$, so s is not a natural cubic spline.
\section*{II.}
\subsection*{(a).}
If using a quadratic spline s to interpolating f, we need to determine three parameters for assuming $ax^2+bx+c$. Now for each interval$[x_i,x_{i+1}]$, we have $f(x_i)$ and $f(x_{i+1})$. So an additional condition is needed to uniquely determine s on $[x_i,x_{i+1}]$. Thus, determining a uniquely s on $[a,b]$ needs an additional condition.
\subsection*{(b).}
$m_i=s'(x_i),p_i=s|_{[x_i,x_{i+1}]}$
\[f(x_i)=f_i,f'(x_i)=m_i,[x_i,x_{i+1}]f=\frac{f_{i+1}-f_i}{x_{i+1}-x_i},[x_i,x_i,x_{i+1}]f=\frac{f_{i+1}-f_i-m_i(x_{i+1}-x_i)}{(x_{i+1}-x_i)^2}\]
So\[s_i(x)=f_i+m_i(x-x_i)+\frac{f_{i+1}-f_i-m_i(x_{i+1}-x_i)}{(x_{i+1}-x_i)^2}(x-x_i)^2\]
 \subsection*{(c)}
 For $m_1$ is given, we can compute $p_1$. From $p_1$ we have $p'(x_2)$, so we can compute $p_2$. Similarly, we can calculate the entire s(x).
 \section*{III.}
 The 2th derivative of $s_1(x)$ is $s''_1(x)=6c(x+1)$, $s_1''(-1)=0$.So we only need to ensure $s_2''(1)=0$;\\
 (\(s_1'(x)=3c(1+x)^2\))
 Assume $s_2(x)=ax^3+bx^2+ex+d$. It satisfies that \[s_1''(0)=s_2''(0),s_2''(1)=0, s_1'(0)=s_2'(0),s_1(0)=s_2(0)\]
 By calculating, \[s_1(0)=1+c, s_1'(0)=3c, s_1''(0)=6c\]
 So \[s_2(0)=d=1+c,s(1)=a+b+e+d=-1,s_2'(0)=e=3c,s_2''(0)=2b=6c,s_2''(1)=6a+2b=0\]
 \[\]
 Solve equations above:\[a=\frac{1}{3},b=-1,c=-\frac{1}{3},d=\frac{2}{3},e=-1\]
 i.e.
 \[c=-\frac{1}{3};\]\[  s_2(x)=\frac{1}{3}x^3-x^2-x+\frac{2}{3}\].
 \section*{IV.}
 \[f(-1)=0,f(0)=1,f(1)=0\]
 \subsection*{(a)}
 Assume $s_i(x)=a_i x^3+b_i x^2+c_i x+d_i$, $i=0,1$. it satisfies \[s(x_i)=f(x_i),s_0'(0)=s_1'(0),s_0''(0)=s_1''(0),s_0''(-1)=0,s_1''(1)=0.\]
 By calculating, we have:
 \[s_0(x)=(-\frac{1}{2})x^3-\frac{3}{2}x^2+1\]
 \[s_1(x)=\frac{1}{2}x^3-\frac{3}{2}x^2+1\]
 \subsection*{(b)}
  \[s_0''(x)=-3x-3\]
 \[s_1''(x)=3x-3\]
  \[E=\int_{-1}^{1}s''(x)^2dx=\int_{-1}^{0}s_0''(x)^2dx+\int_{0}{1}s_1''(x)^2dx=6\]
 \subsubsection*{(i.)}
 Interpolating f by Newton interpolation, we have $q(x)=-x^2+1$,So\\
 \(\int_{-1}^{1}q''(x)^2dx=\int_{-1}^{1}(-2)^2dx=8>E\)
 \subsubsection*{(ii.)}
$f''(x)=-\frac{\pi}{4}cos(\frac{pi}{2}x) $\\we have: \[\int_{-1}^{1}f''(x)^2=\int_{-1}^{1}(-\frac{\pi}{4}cos(\frac{\pi}{2}x))^2dx\]
 \[=\frac{\pi^4}{16}>E\]

 \section*{V.}
 \subsection*{(a)}
 \[ B^2_i(x) = \frac{x - t_{i-1}}{t_{i+1} - t_{i-1}} B^1_i(x) + \frac{t_{i+2} - x}{t_{i+2} - t_i} B^1_{i+1}(x) \]
 
 \[ B^1_i(x) =
 \begin{cases}
 	\frac{x-t_{i-1}}{t_i-t_{i-1}} & \text{if } x \in (t_{i-1}, t_i], \\
 	\frac{t_{i+1}-x}{t_{i+1}-t_{i}} & \text{if} x\in (t_i,t_{i+1}],\\
 	0& \text{otherwise}.
 \end{cases}
 \]
 
 \[ B1_{i+1}(x) =
 \begin{cases}
 	\frac{x-t_{i}}{t_{i+1}-t_{i}} & \text{if } x \in (t_{i}, t_{i+1}], \\
 	\frac{t_{i+2}-x}{t_{i+2}-t_{i+1}} & \text{if } x\in (t_{i+1},t_{i+2}],\\
 	0& \text{otherwise}.
 \end{cases}
 \]
 
 \[ B^2_i(x) =
\begin{cases}
	\frac{x - t_{i-1}}{t_{i+1} - t_{i-1}}\frac{x-t_{i-1}}{t_i-t_{i-1}} & \text{if } x \in (t_{i-1}, t_i], \\
	\frac{x - t_{i-1}}{t_{i+1} - t_{i-1}}\frac{t_{i+1}-x}{t_{i+1}-t_{i}}+\frac{t_{i+2} - x}{t_{i+2} - t_i}\frac{x-t_{i}}{t_{i+1}-t_{i}} & \text{if } x \in (t_i,t_{i+1}],\\
	\frac{t_{i+2} - x}{t_{i+2} - t_i}\frac{t_{i+2}-x}{t_{i+2}-t_{i+1}} & \text{if } x \in (t_{i+1},t_{i+2}],\\
	0& \text{otherwise}.
\end{cases}
\]
 \subsection*{(b)}
 Calculate the derivative of $B^2_i(x)$, we have:
 \[ B^{2'}_i(x) =
\begin{cases}
	2\frac{x - t_{i-1}}{(t_{i+1} - t_{i-1})(t_i-t_{i-1})} & \text{if } x \in (t_{i-1}, t_i], \\
	\frac{t_{i+1}-x}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}-\frac{x-t_{i-1}}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}-\frac{x-t_i}{(t_{i+1}-t_i)(t_{i+2}-t_i)}+\frac{t_{i+2}-x}{(t_{i+2}-t_i)(t_{i+1}-t_i)}& \text{if } x\in (t_i,t_{i+1}]\\
	-2\frac{t_{i+2}-x}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})}& \text{if }x\in (t_{i+1},t_{i+2}]\\
		0& \text{otherwise}.
\end{cases}
\]
$\lim_{x \to t_i^{-}}B^{2'}_i(x)=\lim_{x \to t_i^{-}}2\frac{x - t_{i-1}}{(t_{i+1} - t_{i-1})(t_i-t_{i-1})}=\frac{2}{t_{i+1}-t_{i-1}} $\\
$\lim_{x \to t_i^{+}}B^{2'}_i(x)=\frac{t_{i+1}-x}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}-\frac{x-t_{i-1}}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}-\frac{x-t_i}{(t_{i+1}-t_i)(t_{i+2}-t_i)}+\frac{t_{i+2}-x}{(t_{i+2}-t_i)(t_{i+1}-t_i)}$\\
$=\frac{1}{t_{i+1}-t_{i-1}}-\frac{t_i-t_{i-1}}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}+\frac{1}{t_{i+1}-t_i}=\frac{t_{i+1}-2t_i+t_{i-1}}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}+\frac{1}{t_{i+1}-t_i}=\frac{t_{i+1}-2t_i+t_i+1}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}=\frac{t_{i+1}-t_i}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}$\\
$=\frac{2}{t_{i+1}-t_{i-1}} =\lim_{x \to t_i^{-}}B^{2'}_i(x)$\\
So $\frac{\mathrm{d} B^{2}_i(x)}{\mathrm{d} x} $ is continuous at $t_i$.\\
Now verify the case for $t_{i+1} $ in the same way.\\
 $\lim_{x \to t_{i+1}^{-}}B^{2'}_i(x)=-\frac{t_{i+1}-t_{i-1}}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}-\frac{t_{i+1}-t_i}{(t_{i+1}-t_i)(t_{i+2}-t_i)}+\frac{t_{i+2}-t_{i+1}}{(t_{i+2}-t_i)(t_{i+1}-t_i)}=-\frac{1}{t_{i+1}-t_i}-\frac{1}{t_{i+2}-t_i}+\frac{t_{i+2}-t_{i+1}}{(t_{i+2}-t_i)(t_{i+1}-t_i)}$\\
 $=-\frac{t_{i+2}+t_{i+1}-2t_i}{(t_{i+1-t_i})(t_{i+2}-t_i)}+\frac{t_{i+2}-t_{i+1}}{(t_{i+2}-t_i)(t_{i+1}-t_i)}=-2\frac{t_{i+1}-t_{i}}{(t_{i+2}-t_i)(t_{i+1}-t_i)}=-\frac{2}{t_{i+2}-t_i}$\\
 $\lim_{x \to t_{i+1}^{+}}B^{2'}_i(x)=-2\frac{t_{i+2}-t_{i+1}}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})}=-\frac{2}{t_{i+2}-t_i}=\lim_{x \to t_{i+1}^{-}}B^{2'}_i(x)$\\
 The continuity at $t_{i+1}$ is verified.
 \subsection*{(c)}
 \[ B^{2'}_i(x) =
 \begin{cases}
 	2\frac{x - t_{i-1}}{(t_{i+1} - t_{i-1})(t_i-t_{i-1})} & \text{if } x \in (t_{i-1}, t_i], \\
 	\frac{t_{i+1}-x}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}-\frac{x-t_{i-1}}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}-\frac{x-t_i}{(t_{i+1}-t_i)(t_{i+2}-t_i)}+\frac{t_{i+2}-x}{(t_{i+2}-t_i)(t_{i+1}-t_i)}& \text{if } x\in (t_i,t_{i+1}]\\
 	-2\frac{t_{i+2}-x}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})}& \text{if }x\in (t_{i+1},t_{i+2}]\\
 	0& \text{otherwise}.
 \end{cases}
 \]
 When $x \in (t_{i-1}, t_i]$, let $2\frac{x - t_{i-1}}{(t_{i+1} - t_{i-1})(t_i-t_{i-1})}=0$, the equation holds when $x=t_{i-1}$, which can not be reached. So there is not a zero in this case.
 \\
 Only have to consider this situation $x\in (t_i,t_{i+1}).$\\
 Let $\frac{t_{i+1}-x}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}-\frac{x-t_{i-1}}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}-\frac{x-t_i}{(t_{i+1}-t_i)(t_{i+2}-t_i)}+\frac{t_{i+2}-x}{(t_{i+2}-t_i)(t_{i+1}-t_i)}=0$\\
 Solve the equation, we have:\\
 \[\frac{t_{i+1}+t_{i-1}-2x}{t_{i+1}-t_{i-1}}+\frac{t_i+t_{i+2}-2x}{t_{i+2}-t_i}=0\]
 \[x=\frac{(t_{i+1}+t_{i-1})(t_{i+2}-t_i)+(t_i+t_{i+2})(t_{i+1}-t_{i-1})}{2(t_{i+2}-t_i+t_{i+1}-t_{i-1})}=\frac{t_{i+1}t_{i+2}-t_it_{i-1}}{(t_{i+2}-t_i+t_{i+1}-t_{i-1})}\]
 So only one $x^* \in (t_{i-1},t_{i+1})$ satisfies $.\frac{\mathrm{d} B^{2}_i(x)}{\mathrm{d} x}=0,x^*=\frac{t_{i+1}t_{i+2}-t_it_{i-1}}{t_{i+2}-t_i+t_{i+1}-t_{i-1}}$
 \subsection*{(d)}
Substitute the calculated \(x^*\) into \(B^2_i(x)\) (where \(x^*\) is its unique critical point) and compute the result. We have:
 \[B^2_i(x^*)=\frac{t_{i+2}-t_{i-1}}{t_{i+2}-t_{i-1}+t_{i+1}-t_i}<1 \]
 And by the discussion in (b), we know the derivative of $B^2_i >$ 0 before $x^* <$, 0 after $x^*$, so $B^2_i $reached its max at$ x^*$. On the other hand, $B_i^2 \ge 0$, so $B^2_i(x)\in [0,1).$
 \subsection*{(e)}
 \begin{figure}[h]
 	\centering
 	\includegraphics[width=0.5\textwidth]{figure}
 	\caption{figure}
 	\label{fig:example}
 \end{figure}
 \ref{fig:example}
 The code is in Ve.m.
 \section*{VI.}
By V, we have:

\[ B^2_i(x) =
\begin{cases}
	\frac{x - t_{i-1}}{t_{i+1} - t_{i-1}}\frac{x-t_{i-1}}{t_i-t_{i-1}} & \text{if } x \in (t_{i-1}, t_i], \\
	\frac{x - t_{i-1}}{t_{i+1} - t_{i-1}}\frac{t_{i+1}-x}{t_{i+1}-t_{i}}+\frac{t_{i+2} - x}{t_{i+2} - t_i}\frac{x-t_{i}}{t_{i+1}-t_{i}} & \text{if } x \in (t_i,t_{i+1}],\\
	\frac{t_{i+2} - x}{t_{i+2} - t_i}\frac{t_{i+2}-x}{t_{i+2}-t_{i+1}} & \text{if } x \in (t_{i+1},t_{i+2}],\\
	0& \text{otherwise}.
\end{cases}
\]
So just need to verify the LHS is equal to the equations above.\\
$\begin{aligned}
	&(t_{i+2}-t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t-x)_+^2=[t_{i},t_{i+1},t_{i+2}](t-x)_{+}^{2}-[t_{i-1},t_{i},t_{i+1}](t-x)_{+}^{2} \\
	&=\frac{\frac{(t_{i+2}-x)_{+}^{2}-(t_{i+1}-x)_{+}^{2}}{t_{i+2}-t_{i+1}}-\frac{(t_{i+1}-x)_{+}^{2}-(t_{i}-x)_{+}^{2}}{t_{i+1}-t_{i}}}{t_{i+2}-t_{i}}-\frac{\frac{(t_{i+1}-x)_{+}^{2}-(t_{i}-x)_{+}^{2}}{t_{i+1}-t_{i}}-\frac{(t_{i}-x)_{+}^{2}-(t_{i-1}-x)_{+}^{2}}{t_{i}-t_{i-1}}}{t_{i+1}-t_{i-1}}
\end{aligned}$\\
with the definition of $x^n_+$,\\
$\begin{aligned}
	&\mathrm{when } x\in(t_{i-1},t_{i}], =\frac{(x-t_{i-1})^2}{(t_{i+1}-t_{i-1})(t_i-t_{i-1})} \\
	&\mathrm{when } x\in(t_{i},t_{i+1}], =\frac{(x-t_{i-1})(t_{i+1}-x)}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}+\frac{(t_{i+2}-x)(x-t_i)}{(t_{i+2}-t_i)(t_{i+1}-t_i)} \\
	&\mathrm{when }  x\in(t_{i+1},t_{i+2}], =\frac{(t_{i+2}-x)^2}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})} \\
	&otherwise =0\\
\end{aligned}$\\
 LHS=RHS.
 \section*{VII.}
 $\frac{\mathrm{d}}{\mathrm{d}x}B_i^n(x)=\frac{nB_i^{n-1}(x)}{t_{i+n-1}-t_{i-1}}-\frac{nB_{i+1}^{n-1}(x)}{t_{i+n}-t_i}.(n\ge 2)$\\
 Assume the conclusion holds(i.e.$ B^{n}_i(t_i)=Constant$, for all i),\\
 $\begin{aligned}
 	\boldsymbol\int_{t_{i-1}}^{t_{i+n}}\frac{B_{i}^{n}(x)}{t_{i+n}-t_{i-1}} dx-\int_{t_{i}}^{t_{i+n+1}}\frac{B_{i+1}^{n}(x)}{t_{i+n+1}-t_{i}} dx=\frac1{n+1}\int_{t_{i-1}}^{t_{i+n+1}}\frac{\mathrm{d}}{\mathrm{d}x}B_i^{n+1}(x) dx =\frac{B^{n+1}_i(x)}{n+1}|_{t_{i-1}}^{t_{i+n+1}}=0
 \end{aligned}$\\
 So $\int_{t_{i-1}}^{t_{i+n}}\frac{B_{i}^{n}(x)}{t_{i+n}-t_{i-1}} dx=\int_{t_{i}}^{t_{i+n+1}}\frac{B_{i+1}^{n}(x)}{t_{i+n+1}-t_{i}} dx$, i.e. the integral is independent of its index.
 \section*{VIII.}
 The theorem on expressing complete symmetric polynomials as divided difference of monomials:
 \[
 \forall m \in {N}^+, \quad \forall i \in N, \quad \forall n = 0, 1, \ldots, m,
 \]
 \[
 \tau_{m-n}(x_i, \dots, x_{i+n}) = [x_i, \dots, x_{i+n}] x^m.
 \]
 \subsection*{(a)}
 We have to verify that $\tau_{2}(x_i,\ldots,x_{i+2})=[x_i,\ldots,x_{i+2}]x^4$.\\
 By Thm.3.38:
 \[\tau_{m-n}(x_i,\ldots,x_{i+n})=\sum_{i\leq i_1\leq\ldots\leq i_{m-n}\leq i+n}x_{i_1}x_{i_2}\cdots x_{i_{m-n}}.\]
 By calculating, the table of divided differences for m=4,n=2 :\\
 \(x_i \quad x_i^4\)\\
 \(x_{i+1} \quad x_{i+1}^{4}\quad x_{i+1}^{3}+x_{i+1}^{2}x_{i}+x_{i+1}x_{i}^{2}+x_{i}^{3}\)\\
 \(x_{i+2} \quad x_{i+2}^{4}\quad  x_{i+2}^{3}+x_{i+2}^{2}x_{i+1}+x_{i+2}x_{i+1}^{2}+x_{i+1}^{3}\quad x_{i}^{2}+x_{i+1}^{2}+x_{i+2}^{2}+x_{i}x_{i+1}+x_{i}x_{i+2}+x_{i+1}x_{i+2} \)\\
 So\\
 \[\tau_2(x_i,x_{i+1},x_{i+2})=x_{i}^{2}+x_{i+1}^{2}+x_{i+2}^{2}+x_{i}x_{i+1}+x_{i}x_{i+2}+x_{i+1}x_{i+2} =[x_i,x_{i+1},x_{i+2}]x^4.\]
 \subsection*{(b)}
 Lemma 3.45 (Recursive relations of complete symmetric polynomials). The complete symmetric polynomials satisfy a recursion:
 
 $$\begin{aligned}&\tau_{k+1}(x_1,\ldots,x_n,x_{n+1})=\tau_{k+1}(x_1,\ldots,x_n)+x_{n+1}\tau_k(x_1,\ldots,x_n,x_{n+1}).\end{aligned}$$
 Prove it by induction.\\
 For n=0, the theorem holds clearly for \(\tau_m(x_1)=[x_1]x^m=x_1^m\)\\
 Assume it holds for $n>0$ ,i.e.\[\tau_{m-n}(x, \dots, x_{n}) = [x_1, \dots, x_{n}] x^m.\];\\
 Now need to verify the case when n=k+1(fixed m):
 By the lemma 3.45, \\
$(x_{n+1}-x_1)\tau_{m-n-1}(x_1,\ldots,x_{n+1}) \\
=\tau_{m-n}(x_{1},x_{2},...,x_{n},x_{n+1})-\tau_{m-n}(x_{1},x_{2},...,x_{n})-x_{1}\tau_{m-n-1}(x_{1},...,x_{n},x_{n+1})\\
=\tau_{m-n}(x_{2},...,x_{n},x_{n+1})+x_{1}\tau_{m-n-1}(x_{1},...,x_{n},x_{n+1})-\tau_{m-n}(x_{1},...,x_{n})-x_{1}\tau_{m-n-1}(x_{1},...,x_{n},x_{n+1})\\
=\tau_{m-n}(x_{2},\ldots,x_{n+1})-\tau_{m-n}(x_{1},\ldots,x_{n})\\$
So 
\[\tau_{m-n-1}(x_{1},\ldots,x_{n+1})=[x_{1},\ldots,x_{n+1}]x^{m}\]
So 
\[ \tau_{m-n}(x_i, \dots, x_{i+n}) = [x_i, \dots, x_{i+n}] x^m.\]
 
\end{document}